package buaa.leetcode.DynamicPrograming;

public class UniquePaths62 {
	public static int uniquePaths(int m, int n) {
        if(m == 0 || n == 0){
        	return 0;
        }
        if(m == 1 || n == 1){
        	return 1;
        }
        int[][] t = new int[m+1][n+1];
        for(int i = 0;i< n+1;i++){
        	t[1][i] = 1;
        }
        for(int i = 0;i< m+1;i++){
        	t[i][1] = 1;
        }
        //t[m][n] = 2*uniquePaths(m-1, n-1);
        t[m][n] = uniquePaths(t,m,n); 
		return t[m][n];
    }
	public static int uniquePaths(int[][] t,int m, int n){
		if(t[m][n] > 0){
			return t[m][n];
		}else{
			t[m][n] = uniquePaths(m-1, n)+uniquePaths(m, n-1);
			return t[m][n];
		}
	}
	public static void main(String[] args){
		System.out.println(uniquePaths(3, 3));
	}
}
